package leetcode.tree;

import java.awt.geom.RoundRectangle2D;
import java.util.Properties;

/**
 * @author 榆关
 * 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字
 */
public class ReConstructBinaryTree {
    public TreeNode reConstructBinaryTree(int [] pre, int [] in) {
        TreeNode node = reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
        return node;
    }
    private TreeNode reConstructBinaryTree(int[] pre,int startPre,int endPre,int[] in,int startIn,int endIn){
        //越界作为判定条件
        if(startPre>endPre || startIn > endIn){
            return null;
        }
        //前序遍历的第一个节点为根节点
        TreeNode root = new TreeNode(pre[startPre]);
        for(int i =startIn;i<=endIn;i++){
            if(in[i] == pre[startPre]){
                //找到中序遍历的根节点位置i，左边全部为左节点,i-startIn+startPre为左子树的结束位置。
                root.left = reConstructBinaryTree(pre,startPre+1,i-startIn+startPre,in,startIn,i-1);
                //右边全部为左节点,i-startIn+startPre+为右子树的开始位置。
                root.right = reConstructBinaryTree(pre,i-startIn+startPre+1,endPre,in,i+1,endIn);
                break;
            }
        }
        return root;
    }
}
